class Solution {
    public:
        vector<int> dailyTemperatures(vector<int>& temperatures) {
            stack<int> st;
            int n = temperatures.size();
            vector<int> ans(n,0);
    
            for(int i = 0;i < n;i++){
                while(true){
                    if(st.empty()){
                        break;
                    }else if(temperatures[st.top()] <  temperatures[i]){
                        ans[st.top()] = i - st.top();
                        st.pop();
                    }else{
                        break;
                    }
                }
                st.push(i);
            }
            return ans;
        }
    };
    class Solution {
        public:
            vector<int> dailyTemperatures(vector<int>& temperatures) {
                int n = temperatures.size();
                stack<int> s;
                vector<int> ans(n);
                for(int i = n - 1;i >= 0;i--){
                    while(true){
                        if(s.empty()){
                            ans[i] = 0;
                            break;
                        }else{
                            if(temperatures[s.top()] <= temperatures[i]){
                                s.pop();
                            }else{
                                ans[i] = s.top() - i;
                                break;
                            }
                        }
                    }
                    s.push(i);
                }
                return ans;
            }
        };


        class Solution {
            public:
                vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
                    stack<int> st;
                    int n = nums1.size(),m = nums2.size();
                    unordered_map<int,int> window;
                    for(int i = 0;i < m;i++){
                        while(true){
                            if(st.empty()){
                                break;
                            }else if(nums2[st.top()] > nums2[i]){
                                break;
                            }else{
                                window[nums2[st.top()]] = nums2[i];
                                st.pop();
                            }
                        }
                        
                        st.push(i);
                    }
                    for(int i = 0;i < n;i++){
                        nums1[i] = window[nums1[i]];
                        if(nums1[i] == 0) nums1[i] = -1;
                    }
                    return nums1;
                }
            };

class Solution {
    public:
        vector<int> nextGreaterElements(vector<int>& nums) {
            stack<int> st;
            int n = nums.size();
            vector<int> ans(n, 0);
    
            for (int i = 2 * n - 1; i >= 0; i--) {
                while (true) {
                    if (st.empty()) {
                        if (i < n)
                            ans[i] = -1;
                        break;
                    } else if (nums[st.top()] > nums[i % n]) {
                        if (i < n) {
                            ans[i] = nums[st.top()];
                        }
                        break;
                    } else {
                        st.pop();
                    }
                }
                //  if (!st.empty())
                // cout << st.top() << endl;
                st.push(i % n);
            }
            return ans;
        }
    };

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 class Solution {
    public:
        vector<int> nextLargerNodes(ListNode* head) {
            stack<int> st;
            vector<int> ans;
            vector<int> tmp;
            int pos = 0;
            while(head != nullptr){
                ans.push_back(0);
                tmp.push_back(head->val);
                while(true){
                    if(st.empty()){
                        break;
                    }else if(tmp[st.top()] >= head->val){
                        break;
                    }else{
                        ans[st.top()] = head->val;
                        st.pop();
                    }
                }
                head = head->next;
                st.push(pos);
                pos++;
            }
            return ans;
        }
    };

    class StockSpanner {
        public:
            stack<int> st1,st2;
            vector<int> vi1,vi2;
            StockSpanner() {
                vi1.clear(),vi2.clear();
            }
            
            int next(int price) {
                int ans = 0;
                int pos = vi1.size() - 1;
                while(pos >= 0 && price >= vi1[pos]){
                    pos -= vi2[pos];
                }
                vi1.push_back(price);
        
                ans = vi1.size() - pos - 1;
                vi2.push_back(ans);
                // ans = max(ans,1);
                // cout << ans << endl;
                return ans;
            }
        };
        
        /**
         * Your StockSpanner object will be instantiated and called as such:
         * StockSpanner* obj = new StockSpanner();
         * int param_1 = obj->next(price);
         */

1
class Solution {
    public:
        int carFleet(int target, vector<int>& position, vector<int>& speed) {
            int n = position.size();
            vector<vector<int> > vv(n,vector<int>(2));
            for(int i = 0;i < n;i++){
                vv[i][0] = position[i],vv[i][1] = speed[i];
            }
            double oldtime = -1;
            int ans = 0;
            sort(vv.begin(),vv.end());
            for(int i = n - 1;i >=0;i--){
                double len = target - vv[i][0];
                double v   = vv[i][1];
                // cout << len/v <<':' << endl;
                if(oldtime >= len/v){
                    // 赶上了
                    ;
                }else{
                    // cout <<i << endl;
                    ans++;
                    oldtime = len/v;
                }
            }
            return ans;
        }
    };